home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Tools / Languages / Caml Light 0.61 / Source / src / lib / set.mli < prev    next >
Encoding:
Text File  |  1993-09-24  |  2.6 KB  |  56 lines  |  [TEXT/MPS ]
  1. (* Sets over ordered types *)
  2.  
  3. (* This module implements the set data structure, given a total ordering
  4.    function over the set elements. All operations over sets
  5.    are purely applicative (no side-effects).
  6.    The implementation uses balanced binary trees, and is therefore
  7.    reasonably efficient: insertion and membership take time
  8.    logarithmic in the size of the set, for instance. *)
  9.  
  10. type 'a t;;
  11.         (* The type of sets containing elements of type ['a]. *)
  12.  
  13. value empty: ('a -> 'a -> int) -> 'a t
  14.         (* The empty set.
  15.            The argument is a total ordering function over the set elements.
  16.            This is a two-argument function [f] such that
  17.            [f e1 e2] is zero if the elements [e1] and [e2] are equal,
  18.            [f e1 e2] is strictly negative if [e1] is smaller than [e2],
  19.            and [f e1 e2] is strictly positive if [e1] is greater than [e2].
  20.            Examples: a suitable ordering function for type [int]
  21.            is [prefix -]. For type [string], you could use
  22.            [compare_strings]. *)
  23.   and is_empty: 'a t -> bool
  24.         (* Test whether a set is empty or not. *)
  25.   and mem: 'a -> 'a t -> bool
  26.         (* [mem x s] tests whether [x] belongs to the set [s]. *)
  27.   and add: 'a -> 'a t -> 'a t
  28.         (* [add x s] returns a set containing all elements of [s],
  29.            plus [x]. If [x] was already in [s], [s] is returned unchanged. *)
  30.   and remove: 'a -> 'a t -> 'a t
  31.         (* [remove x s] returns a set containing all elements of [s],
  32.            except [x]. If [x] was not in [s], [s] is returned unchanged. *)
  33.   and union: 'a t -> 'a t -> 'a t
  34.   and inter: 'a t -> 'a t -> 'a t
  35.   and diff: 'a t -> 'a t -> 'a t
  36.         (* Union, intersection and set difference. *)
  37.   and equal: 'a t -> 'a t -> bool
  38.         (* [equal s1 s2] tests whether the sets [s1] and [s2] are
  39.            equal, that is, contain the same elements. *)
  40.   and compare: 'a t -> 'a t -> int
  41.         (* Total ordering between sets. Can be used as the ordering function
  42.            for doing sets of sets. *)
  43.   and elements: 'a t -> 'a list
  44.         (* Return the list of all elements of the given set.
  45.            The elements appear in the list in some non-specified order. *)
  46.   and iter: ('a -> 'b) -> 'a t -> unit
  47.         (* [iter f s] applies [f] in turn to all elements of [s], and
  48.            discards the results. The elements of [s] are presented to [f]
  49.            in a non-specified order. *)
  50.   and fold: ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
  51.         (* [fold f s a] computes [(f xN ... (f x2 (f x1 a))...)],
  52.            where [x1 ... xN] are the elements of [s].
  53.            The order in which elements of [s] are presented to [f] is
  54.            not specified. *)
  55. ;;
  56.